import java.util.Arrays;

public class test5 {
    public int largestSumAfterKNegations(int[] nums, int k) {
        int m = 0;
        int min=Integer.MAX_VALUE;
        for (int x:nums) {
            if(x<0) m++;
            min = Math.min(min,Math.abs(x));
        }

        int sum = 0;
        if(m>k){
            Arrays.sort(nums);
            for (int i = 0; i < k; i++) {
                sum-=nums[i];
            }
            for (int i = k; i < nums.length; i++) {
                sum+=nums[i];
            }
        }else {
            // 负数全部变成正数
            for (int x:nums) {
                sum+=Math.abs(x);
            }
            if((k-m)%2!=0)
                sum -= min*2;
        }
        return sum;
    }
}
